#define _CRT_SECURE_NO_WARNINGS
//class Solution {
//public:
//    int subarraySum(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        hash[0]++;
//        int sum = 0, ret = 0;
//        for (auto& e : nums)
//        {
//            sum += e;
//            if (hash.count(sum - k))
//            {
//                ret += hash[sum - k];
//            }
//            hash[sum]++;
//        }
//        return ret;
//    }
//};

#include <vector>
#include <iostream>
using namespace std;

void adjustDown(vector<int>& nums, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && nums[child + 1] > nums[child])  child++;
		if (nums[child] > nums[parent])  swap(nums[child], nums[parent]);
		parent = child;
		child = parent * 2 + 1;
	}
}
void heapSort(vector<int>& nums)
{
	int n = nums.size();
	for (int i = n - 1 - 1 / 2; i >= 0; i--)
	{
		adjustDown(nums, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(nums[0], nums[end]);
		end--;
		adjustDown(nums, 0, end + 1);
	}
}
int main()
{
	vector<int> nums = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	heapSort(nums);
	for (auto& e : nums)  cout << e << " ";
	cout << endl;
	return 0;
}